package puf.m2.regular.converter;

import java.util.Iterator;
import java.util.Set;

import puf.m2.automaton.AbstractFiniteAutomaton;
import puf.m2.automaton.State;
import puf.m2.automaton.Transition;
import puf.m2.automaton.Word;
import puf.m2.regular.Discretizer;
import puf.m2.regular.TileRegExp;

/**
 * This class moderates the conversion of a regular expression to
 * a two-way automaton.
 */
public class REToTWAConverter {
    //TODO Convert RE to a non-deterministic 2wa.
    //TODO Convert the non-determ 2wa to determ 2wa

    /** The regular expression of tile, which is being processed. */
    private TileRegExp regexp;
    /** The automaton being built, which will be modified throughout this process. */
    private AbstractFiniteAutomaton automaton;

    /** The set of transitions that still require expansion. */
    private Set<Transition> toDo;

    /** The current action, or 0 if no action. */
    private int action = 0;

    /** The transition being replaced. */
    private Transition transition = null;

    /** The number of transitions needed for the current step. */
    private int transitionNeeded = 0;

    /** The replacement transitions. */
    private Transition[] replacements = null;

    /**
     * The codes for actions on an expression, which are, in order, that
     * parentheses are to be taken out, that an expression is to be "destarred",
     * or that ors or concatenations are to be broken into their respective
     * parts.
     */
    private static final int DEPARENS = 1, DESTAR = 2, DEOR = 3, DECAT = 4;

    public REToTWAConverter(TileRegExp exp) {
        regexp = exp;
        automaton = new AbstractFiniteAutomaton();
    }

    /**
     * This will return the action that are necessary for a given subexpression.
     * If this method returns 0, that indicates that no action is required.
     *
     * @param expr
     *            the expression to check for actions that may be required
     */
    private int requiredAction(String expr) {
        if (expr.length() <= 1)
            return 0;
        if (Discretizer.or(expr).length > 1)
            return DEOR;
        if (Discretizer.cat(expr).length > 1)
            return DECAT;
        if (expr.charAt(expr.length() - 1) == '*')
            return DESTAR;
        if (expr.charAt(0) == '('
                && expr.charAt(expr.length() - 1) == ')')
            return DEPARENS;
        throw new IllegalArgumentException("Expression " + expr
                + " not recognized!");
    }

    /**
     * Given a transition to replace, and a list of the strings the transition
     * is being broken into, modify the automaton so that that transition is
     * replaced with a sequence of transitions each corresponding to the array.
     *
     * @param transition
     *            the transition to replace
     * @param exps
     *            the array of string expressions to replace the transition with
     * @return the array of transitions created
     */
    private Transition[] replaceTransition(Transition transition,
            String[] exps) {
        Transition[] t = new Transition[exps.length];
        automaton.removeTransition(transition);
        for (int i = 0; i < exps.length; i++) {
            State s = automaton.createState();
            State e = automaton.createState();
            t[i] = new Transition(s, e, exps[i]);
            automaton.addTransition(t[i]);
            if (requiredAction(t[i].label()) != 0)
                toDo.add(t[i]);
        }
        return t;
    }

    /**
     * Called when a transition is selected with the deexpressionifier tool.
     *
     * @param transition
     *            the transition that was clicked
     */
    public void transitionCheck(Transition transition) {
        if (action != 0)
            return;

        if ((action = requiredAction(transition.label())) == 0)
            return;

        this.transition = transition;
        toDo.remove(transition);
        String label = transition.label();
        switch (action) {
        case DEPARENS: {
            State s1 = transition.source();
            State s2 = transition.target();
            String newLabel = Discretizer.deEpsilon(label.substring(1, label
                    .length() - 1));
            automaton.removeTransition(transition);
            Transition t = new Transition(s1, s2, newLabel);
            automaton.addTransition(t);
            if (requiredAction(newLabel) != 0)
                toDo.add(t);
            action = 0; // That's all that need be done.
            break;
        }
        case DESTAR:
            replacements = replaceTransition(transition,
                    new String[] { Discretizer.deEpsilon(label.substring(0,
                            label.length() - 1)) });
            transitionNeeded = 4;
            break;
        case DEOR:
            replacements = replaceTransition(transition, Discretizer.or(label));
            transitionNeeded = 2 * replacements.length;
            break;
        case DECAT:
            replacements = replaceTransition(transition, Discretizer.cat(label));
            transitionNeeded = replacements.length + 1;
            break;
        }
        nextStep();
    }

    /**
     * Creates a epsilon-transition between two states.
     * @param from
     *            the from state
     * @param to
     *            the to state
     * @return a epsilon-transition between those states
     */
    private Transition epsilon(State from, State to) {
        return new Transition(from, to, "");
    }

    public void completeStep() {
        if (action == 0) {
            Iterator<Transition> it = toDo.iterator();
            Transition t = it.next();
            transitionCheck(t);
        }
        State from = transition.source();
        State to = transition.target();
        switch (action) {
        case DEPARENS:
            // Probably a deparenthesization, or whatever.
            return;
        case DEOR:
            for (int i = 0; i < replacements.length; i++) {
                automaton.addTransition(epsilon(from, replacements[i].source()));
                automaton.addTransition(epsilon(replacements[i].target(), to));
            }
            break;
        case DECAT:
            automaton.addTransition(epsilon(from, replacements[0].source()));
            for (int i = 0; i < replacements.length - 1; i++)
                automaton.addTransition(epsilon(replacements[i].target(),
                        replacements[i + 1].source()));
            automaton.addTransition(epsilon(
                    replacements[replacements.length - 1].target(), to));
            break;
        case DESTAR:
            automaton.addTransition(epsilon(from, replacements[0].source()));
            automaton.addTransition(epsilon(replacements[0].target(), to));
            automaton.addTransition(epsilon(from, to));
            automaton.addTransition(epsilon(to, from));
            break;
        }
        transitionNeeded = 0;
        nextStep();
    }

    /**
     * Does everything.
     */
    public void completeAll() {
        while (action != 0 || toDo.size() > 0)
            completeStep();
    }

    public void nextStep() {
        // if all done
        if (transitionNeeded == 0) {
            action = 0;
            return;
        }

        // just for debug purpose
        switch (action) {
        case DEOR:
            System.out.println("De-oring " + transition.label());
            break;
        case DECAT:
            System.out.println("De-concatenating " + transition.label());
            break;
        case DESTAR:
            System.out.println("De-staring " + transition.label());
            break;
        }
    }

    public boolean convert() {
        // check the input
        try {
            regexp.asCheckedString();
        } catch (UnsupportedOperationException e) {
            System.out.println("Illegal Expression: " + e.getMessage());
            return false;
        }

        // initialize the automaton
        State initialState = automaton.createState();
        State finalState = automaton.createState();
        automaton.setInitialState(initialState);
        automaton.addFinalState(finalState);
        Transition initialTransition = new Transition(initialState, finalState,
                Discretizer.deEpsilon(regexp.toString().replace("!", Word.EPSILON)));
        automaton.addTransition(initialTransition);

        // determine the next action
        if (requiredAction(initialTransition.label()) != 0)
            toDo.add(initialTransition);
        nextStep();
        completeAll();

        // convert to two-way deterministic automaton - 2dfa
        //TODO
        return true;
    }
}
